package com.cqs.leetcode;

/**
 * Created by cqs on 2018/3/26.
 */
public class LongestWordDictionary {

    //'$'代替'空'字符
    private Trie root = new Trie('$', 0);

    private class Trie {
        char value;
        int count;
        Trie[] children = new Trie[26];

        Trie(char value, int count) {
            this.value = value;
            this.count = count;
        }
    }

    private void buildTrieTree(String[] words) {
        if (words != null) {
            for (String word : words) {
                insert(word);
            }
        }
    }

    private void insert(String word) {
        Trie trie = root;
        if (word != null && word.length() > 0) {
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                int index = c - 97;
                if (trie.children[index] == null) {
                    trie.children[index] = new Trie(c, 0);
                }
                trie = trie.children[index];
            }
            if (trie != null) {
                trie.count++;
            }
        }
    }


    private boolean searchWord(String word) {
        if (word != null) {
            Trie trie = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                int index = c - 97;
                trie = trie.children[index];
                if (trie == null || trie.value != c || trie.count < 1) {
                    return false;
                }
            }
        }
        return true;
    }


    public String longestWord(String[] words) {
        int maxLen = 0;
        buildTrieTree(words);
        String result = "";
        for (String word : words) {
            if (word.length() >= maxLen) {
                boolean exist = searchWord(word);
                if (exist) {
                    //maxLen = Math.max(maxLen,word.length());
                    boolean isSameLen = word.length() == maxLen;
                    if (word.length() > maxLen || (isSameLen && word.compareTo(result) < 0)) {
                        result = word;//更新结果
                    }
                    maxLen = word.length();
                }
            }
        }
        return result;
    }


    private boolean exists(String str) {
        if (str != null) {
            Trie trie = root;
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                int index = c - 97;
                trie = trie.children[index];
                if (trie == null || trie.value != c) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        LongestWordDictionary l = new LongestWordDictionary();
        String[] words = {"a", "banana", "app", "appl", "ap", "apply", "apple"};

        String result = l.longestWord(words);
        System.out.println(result);


    }

}
